// 1. 解法1：递归 分治
function subsets(nums: number[]): number[][] {
    if (nums.length === 0) {
        return [[]];
    }
    if (nums.length === 1) {
        return [[], nums];
    }
    let res: number[][] = []
    const divideConquer = function (index: number, nums: number[], result: number[] = []) {
        // 1.terminator
        if (index === nums.length) {
            res.push(result)
            return
        }
        // 2. process ,split you big problems
        // 添加nums[index], 或不添加nums[index]
        // 3. 进入下一层，index ++；
        divideConquer(index+1, nums, [...result])
        divideConquer(index+1, nums, [...result, nums[index]])
        // 4. merge rsult
        // 5. reverse state
    }
    divideConquer(0, nums, [])
    return res
};

// 1. 解法2：迭代
function subsets2(nums: number[]): number[][] {
    if (nums.length === 0) {
        return [[]];
    }
    if (nums.length === 1) {
        return [[], nums];
    }
    let result:number[][] = [[]]
    for(let i of nums){
        // 每次迭代 
        // 把result中的每个元素item拿出来，然后item上面追加一个当前i，
        // 然后再把这个追加i的元素，添加到result中。
        let tempArr:number[][]=[];
        result.forEach(item=>tempArr.push( [...item,i]))
        result = result.concat(tempArr)
    }
    return result;
};
